#include<bits/stdc++.h>
using namespace std;
int n,k,a[100005],g[100005],f[100005],cnt,ans,res;
int t[10000007][5],tag[10000007][5];// 最多
int t2[10000007][5],tag2[10000007][5]; //最少
struct node{
	int s,id;
}b[100005];
int cmp(node x,node y){
	if(x.s==y.s) return x.id<y.id;
	return x.s<y.s;
}
void build(int now,int l,int r,int K){
	if(l==r){t[now][K]=0;tag[now][K]=0;return ;}
	build(now*2,l,(l+r)/2,K);
	build(now*2+1,(l+r)/2+1,r,K);
}
void build2(int now,int l,int r,int K){
	if(l==r){t2[now][K]=n+1;tag[now][K]=n+1;return ;}
	build2(now*2,l,(l+r)/2,K);
	build2(now*2+1,(l+r)/2+1,r,K);
	tag2[now][K]=n+1;
}
void updown(int now,int l,int r,int K){
	int mid=(l+r)/2;
	if(l==mid) t[now*2][K]=max(t[now*2][K],tag[now][K]);
	else tag[now*2][K]=max(tag[now*2][K],tag[now][K]);
	if(mid+1==r) t[now*2+1][K]=max(t[now*2+1][K],tag[now][K]);
	else tag[now*2+1][K]=max(tag[now*2+1][K],tag[now][K]);
	tag[now][K]=0;
}
void add(int now,int l,int r,int L,int R,int x,int K){
	if(L<=l && r<=R){
		if(l==r){
			t[now][K]=max(t[now][K],x);
			return ;
		}
		else {
			tag[now][K]=max(tag[now][K],x);
			return ;
		}
	} updown(now,l,r,K);
	int mid=(l+r)/2;
	if(L<=mid) add(now*2,l,mid,L,R,x,K);
	if(mid+1<=R) add(now*2+1,mid+1,r,L,R,x,K);
}
void updown2(int now,int l,int r,int K){
	int mid=(l+r)/2;
	if(l==mid) t2[now*2][K]=min(t2[now*2][K],tag2[now][K]);
	else tag2[now*2][K]=min(tag2[now*2][K],tag2[now][K]);
	if(mid+1==r) t2[now*2+1][K]=min(t2[now*2+1][K],tag2[now][K]);
	else tag2[now*2+1][K]=min(tag2[now*2+1][K],tag2[now][K]);
	tag2[now][K]=n+1;
}
void add2(int now,int l,int r,int L,int R,int x,int K){
	if(L<=l && r<=R){
		if(l==r){
			t2[now][K]=min(t2[now][K],x);
			return ;
		}
		else {
			tag2[now][K]=min(tag2[now][K],x);
			return ;
		}
	} updown2(now,l,r,K);
	int mid=(l+r)/2;
	if(L<=mid) add2(now*2,l,mid,L,R,x,K);
	if(mid+1<=R) add2(now*2+1,mid+1,r,L,R,x,K);
}
void query(int now,int l,int r){
	if(l==r){
//		cout<<" > "<<l<< " : "<<t[now]<<" "<<t2[now]<<'\n';
//		ans+=t[now]-t2[now]+1;
		int maxn=t[now][1],minn=t2[now][1];
		for(int i=1;i<=k;i++){
			maxn=min(t[now][i],maxn),minn=max(t2[now][i],minn);
//			cout<<" > "<<l<<" "<<i<<" : "<<t[now][i]<<'\n'; 
//			cout<<" > "<<l<<" "<<i<<" : "<<t2[now][i]<<'\n'; 
		}
		ans=ans+max(0,maxn-minn+1);
		return ;
	}
	for(int i=1;i<=k;i++) 
		updown(now,l,r,i), updown2(now,l,r,i);
	query(now*2,l,(l+r)/2);
	query(now*2+1,(l+r)/2+1,r);
}
signed main(){
	freopen("reporter.in","r",stdin);
	freopen("reporter.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i],b[i].s=a[i],b[i].id=i;
	if(n<=1000){
		for(int i=1;i<=n;i++){
			cnt=0; f[0]=2*n;
			for(int i=1;i<=n;i++) g[i]=f[i]=0;
			for(int j=i;j<=n;j++){
				g[a[j]]++;
				f[g[a[j]]-1]--;
				f[g[a[j]]]++;
				if(f[g[a[j]]-1]==0 && g[a[j]]-1<=cnt) cnt=g[a[j]]-2;
				while(f[cnt+1]>=1) cnt++;
				if(cnt>=k) ans++;
			}
		}
		cout<<ans;
		return 0;
	}
	sort(b+1,b+n+1,cmp); 
	build2(1,1,n,1);
	build2(1,1,n,2);
	build2(1,1,n,3);
	build2(1,1,n,4);
	build(1,1,n,1);
	build(1,1,n,2);
	build(1,1,n,3);
	build(1,1,n,4);
	for(int i=1;i<=n;i++){
		int opt=n; res=0;
		for(int j=i+1;j<=n;j++)
			if(b[j].s!=b[j-1].s) {opt=j-1;break;}
		g[++res]=0;
		for(int j=i;j<=opt;j++) g[++res]=b[j].id;
		g[++res]=n+1;
		for(int K=1;K<=k;K++){
			for(int j=1;j+K-1+2<=res;j++){
//				cout<<" > max "<<K<<"("<<b[i].s<<")"<<" : "<<g[j]+1<<" "<<g[j+1]<<" : "<<g[j+K-1+2]-1<<'\n';
//				cout<<" > min "<<K<<"("<<b[i].s<<")"<<" : "<<g[j]+1<<" "<<g[j+1]<<" : "<<g[j+K-1+2-1]<<'\n';
				add(1,1,n,g[j]+1,g[j+1],g[j+K-1+2]-1,K);
				add2(1,1,n,g[j]+1,g[j+1],g[j+K-1+2-1],K);
			}
		}
		i=opt;
	}
	query(1,1,n);
	cout<<ans;
	return 0;
}
